The semiconductor integrated circuit (IC) industry has experienced rapid growth. In the course of IC evolution, functional density (i.e., the number of interconnected devices per chip area) has generally increased while geometry size (i.e., the smallest component (or line) that can be created using a fabrication process) has decreased. This scaling down process generally provides benefits by increasing production efficiency and lowering associated costs. Such scaling down has also increased the complexity of processing and manufacturing ICs and, for these advances to be realized, similar developments in IC manufacturing are needed.
For example, as the geometry sizes shrink, it generally becomes difficult for conventional photolithography processes to form semiconductor features having these small geometry sizes. One approach to this issue uses a double patterning (DP) method. A typical DP method decomposes an IC layout into two subsets and fabricates a photomask for each subset. A wafer is patterned with the two photomasks in two lithography processes. Images of the two lithography processes overlay with one another to collectively produce a denser image on the wafer. However, as the geometry sizes continue shrinking, even DP methods are not enough for meeting pattern density requirements in some instances.
One alternative approach uses multiple patterning (MP) method where an IC layout is decomposed into N subsets (throughout the present disclosure, N is an integer greater than 2 unless otherwise specified). Correspondingly, at least N photomasks are fabricated to collectively image the IC layout onto a wafer. However, implementing an MP method for IC design and fabrication is challenging as the MP decomposition is analogous to the N-coloring problem in mathematics, which has been shown to be an NP-complete problem. Therefore, it is desirable to find a practical way of realizing MP methods for IC design and fabrication.